package OLa;

import DFS.CollectCollection;
import DFS.Graph;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Hierholzer算法求解欧拉回路
 */
public class EulerLoop {
    private Graph graph;

    public EulerLoop(Graph graph) {
        this.graph = graph;
    }

    public boolean hasEulerLoop() {
        CollectCollection cc = new CollectCollection(graph);
        if (cc.count() > 1) {
            return false;
        }
        for (int v = 0; v < graph.getVertexNum(); v++) {
            if (graph.degree(v) % 2 == 1) {
                return false;
            }
        }
        return true;
    }

    public List<Integer> result() {
        List<Integer> res = new ArrayList<>();
        if (!hasEulerLoop()) {
            return res;
        }
        Graph cloneGraph = (Graph) graph.clone();
        Stack<Integer> stack = new Stack<>();
        int curV = 0;
        stack.push(curV);
        while (!stack.empty()) {
            if (cloneGraph.degree(curV) != 0) {
                stack.push(curV);
                int w = cloneGraph.adj(curV).iterator().next();
                cloneGraph.removeEdge(curV, w);
                curV = w;
            } else {
                res.add(curV);
                curV = stack.pop();
            }
        }
        return res;
    }

    public static void main(String[] a) {
        Graph graph = new Graph("Olag.txt");
        EulerLoop eulerLoop = new EulerLoop(graph);
        System.out.println(eulerLoop.result());
        Graph graph2 = new Graph("Olag2.txt");
        EulerLoop eulerLoop2 = new EulerLoop(graph2);
        System.out.println(eulerLoop2.result());
    }
}
